package xio.leetcode.java;


import xio.leetcode.java.base.ListNode;
import xio.leetcode.java.test.LinkedListUtils;

public class ListMergeSort {
//    找到链表中间的节点

    public static ListNode getMiddle(ListNode head) {
        if (head == null)
            return null;
        ListNode fast, slow;
        fast = head;
        slow = head;
        while (slow.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //  合并链表
    public static ListNode merge(ListNode a, ListNode b) {
        ListNode curr, dummyHead;
        dummyHead = new ListNode(0);
        curr = dummyHead;
//        dummyHead=curr.next;说明指针
        while (a != null && b != null) {
            if (a.val < b.val) {
                curr.next = a;
                a = a.next;
            } else {
                curr.next = b;
                b = b.next;
            }
            curr = curr.next;
        }
        curr.next = (a == null) ? b : a;
        return dummyHead.next;//选择用dummyHead的原因是必须记录新的链表的初始位置
    }

    //    单链表的归并排序
    public static ListNode merge_sort(ListNode head) {
        if (head == null || head.next == null)
            return head;
//        得到链表中间的节点
        ListNode middle = getMiddle(head);
        ListNode sHalf = middle.next;
//        拆分链表
        middle.next = null;
        return merge(merge_sort(head), merge_sort(sHalf));
    }

    //  主函数，建立初始链表来调用
    public static void main(String[] args) {
        // 生成链表 4 -> 2 -> 1 -> 3
        ListNode head = LinkedListUtils.generateLinkedList(3,2,4);
        // 测试，并输出
        LinkedListUtils.printLinkedList(merge_sort(head));
    }
}
